public class Solution {
    /*
        解法1：哈希表
        时间：O（m+n）
        空间：O（m）或O（n）
    */
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        Map<ListNode,String> map = new HashMap<>();
        while(headA != null){
            map.put(headA,"tmp");
            headA = headA.next;
        }
        ListNode res = null;
        while(headB != null){
            if( map.containsKey(headB)==true ){
                res = headB;
                break;
            }
            headB = headB.next;
        }
        return res;
    }
}

public class Solution {
    /*
        解法2：双指针法
        思路：对的人即使错过了也会在同一时间相遇
            {
                加入链表相交，求的是第一个相交的节点，则对于A,B来说，第一个相交节点后的
                路程都是一致的，则：
                在某一时刻 pApA 和 pBpB 相遇，则 pA pB 为相交结点
            }
        时间：O（m+n）
        空间：O（1）
    */
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        ListNode res = null;
        ListNode pa = headA, pb = headB;
        /*
            为什么要cnt的原因：while循环的退出条件是 pa!=null && pb!=null，

        */
        // int cn1 = 0,cn2 = 0;
        // while(pa!=null && pb!=null){
        //     // System.out.println("A:"+pa.val+",B:"+pb.val);
        //     if(pa == pb){
        //         res = pa;
        //         break;
        //     }
        //     pa = pa.next;
        //     pb = pb.next;
        //     if(pa == null && cn1 == 0){
        //         pa = headB;
        //         cn1 ++;
        //     }
        //     if(pb == null && cn2 == 0){
        //         pb = headA;
        //         cn2 ++;
        //     }
        // }
        // return res;

        /*
            pa==pb有两种情况，一种是第一个相交的节点，此时pa==pb！=null
            还有一种情况是 pa==pb==null
        */  
        while( pa!=pb ){
            pa = ( pa==null ? headB : pa.next);
            pb = ( pb==null ? headA : pb.next );
        }
        /*
            2021.3.28
            我的错误解法：
            while( p1!=p2 ){
                p1 = p1.next;
                p2 = p2.next;
                if(p1==null) p1 = headB;
                if(p2==null) p2 = headA;
            }   
        */
        return pa;
    }
}